Restricted sumset

In additive number theory and combinatorics, a restricted sumset has the form

S=\{a_1%2B\cdots%2Ba_n:\ a_1\in A_1,\ldots,a_n\in A_n \ \mathrm{and}\ P(a_1,\ldots,a_n)\not=0\},

where A_1,\ldots,A_n are finite nonempty subsets of a field F and P(x_1,\ldots,x_n) is a polynomial over F.

When P(x_1,\ldots,x_n)=1, S is the usual sumset A_1%2B\cdots%2BA_n which is denoted by nA if A_1=\cdots=A_n=A; when

P(x_1,\ldots,x_n)=\prod_{1\le i<j\le n}(x_j-x_i),

S is written as A_1\dotplus\cdots\dotplus A_n which is denoted by n^{\wedge} A if A_1=\cdots=A_n=A. Note that |S|>0 if and only if there exist a_1\in A_1,\ldots,a_n\in A_n with P(a_1,\ldots,a_n)\not=0.

Contents

Cauchy-Davenport theorem

The Cauchy–Davenport theorem named after Augustin Louis Cauchy and Harold Davenport asserts that for any prime p and nonempty subsets A and B of the field \Bbb Z/p\Bbb Z we have the inequality

|A%2BB|\ge\min\{p,\ |A|%2B|B|-1\}.\,

Erdős–Heilbronn conjecture

The Erdős–Heilbronn conjecture posed by Paul Erdős and Hans Heilbronn in 1964 states that |2^\wedge A|\ge\min\{p,2|A|-3\} if p is a prime and A is a nonempty subset of the field \Bbb Z/p\Bbb Z. This was first confirmed by J. A. Dias da Silva and Y. O. Hamidoune in 1994[1] who showed that

|n^\wedge A|\ge\min\{p(F),\ n|A|-n^2%2B1\},

where A is a finite nonempty subset of a field F, and p(F) is a prime p if F is of characteristic p, and p(F)=\infty if F is of characteristic 0. Various extensions of this result were given by Noga Alon, M. B. Nathanson and I. Ruzsa in 1996,[2] Q. H. Hou and Zhi-Wei Sun in 2002,[3] and G. Karolyi in 2004.[4]

Combinatorial Nullstellensatz

A powerful tool in the study of lower bounds for cardinalities of various restricted sumsets is the following fundamental principle: the combinatorial Nullstellensatz.[5] Let f(x_1,\ldots,x_n) be a polynomial over a field F. Suppose that the coefficient of the monomial x_1^{k_1}\cdots x_n^{k_n} in f(x_1,\ldots,x_n) is nonzero and k_1%2B\cdots%2Bk_n is the total degree of f(x_1,\ldots,x_n). If A_1,\ldots,A_n are finite subsets of F with |A_i|>k_i for i=1,\ldots,n, then there are a_1\in A_1,\ldots,a_n\in A_n such that f(a_1,\ldots,a_n)\not=0.

The method using the combinatorial Nullstellensatz is also called the polynomial method. This tool was rooted in a paper of N. Alon and M. Tarsi in 1989,[6] and developed by Alon, Nathanson and Ruzsa in 1995-1996,[2] and reformulated by Alon in 1999.[5]

References

  1. ^ Dias da Silva, J. A.; Hamidoune, Y. O. (1994). "Cyclic spaces for Grassman derivatives and additive theory". Bulletin of the London Mathematical Society 26 (2): 140–146. doi:10.1112/blms/26.2.140. 
  2. ^ a b Alon, Noga; Nathanson, Melvyn B.; Ruzsa, Imre (1996). "The polynomial method and restricted sums of congruence classes". Journal of Number Theory 56 (2): 404–417. doi:10.1006/jnth.1996.0029. MR1373563. http://www.math.tau.ac.il/~nogaa/PDFS/anrf3.pdf. 
  3. ^ Hou, Qing-Hu; Sun, Zhi-Wei (2002). "Restricted sums in a field". Acta Arithmetica 102 (3): 239–249. doi:10.4064/aa102-3-3. MR1884717. 
  4. ^ Károlyi, Gyula (2004). "The Erdős–Heilbronn problem in abelian groups". Israel Journal of Mathematics 139: 349–359. doi:10.1007/BF02787556. MR2041798. 
  5. ^ a b Alon, Noga (1999). "Combinatorial Nullstellensatz". Combinatorics, Probability and Computing 8 (1–2): 7–29. doi:10.1017/S0963548398003411. MR1684621. http://www.math.tau.ac.il/~nogaa/PDFS/null2.pdf. 
  6. ^ Alon, Noga; Tarsi, Michael (1989). "A nowhere-zero point in linear mappings". Combinatorica 9 (4): 393–395. doi:10.1007/BF02125351. MR1054015. 

External links